1. Field of the Invention
Methods consistent with the present invention relate to key management for broadcast encryption, and more particularly, to key management for broadcast encryption in a tree topology network.
2. Description of the Related Art
Broadcast encryption (BE) is a technique for a transmitter, that is, a broadcast center, to effectively transmit information only to intended users among all users. The BE needs to effectively work in a case where the aggregation of the users who are to receive the information changes arbitrarily and dynamically. An important property of the BE is to revoke or exclude unintended users, for example, illegal users or expired users.
FIG. 1 illustrates a network of a data transmission system according to a conventional BE. Referring to FIG. 1, a content producer 100 creates various usable data such as audio data and video data, and provides the created data to a service provider 110. The service provider 110 broadcasts the data, which is provided from the content producer 100, to authorized users, who have paid for the data, via wired and wireless communication networks such as a mobile digital right management (DRM) network 140 or a smart home DRM network 150.
Specifically, the service provider 110 can transfer data to users' devices such as set-top boxes 141 equipped with satellite receivers via a satellite 120 and transfer data to a mobile communication terminal 142 via a mobile communication network. In addition the service provider 110 can transfer data to terminals 150 through 155 in the smart home DRM network 150 over an Internet 130.
During such data transmissions, data are encrypted using the BE so as to prevent an illegal user 160 who has not paid for the data from acquiring and utilizing the data.
Security of the encryption and decryption systems depends on a system which is responsible for the encryption key management. An important concern of the encryption key management system is how to derive encryption keys. How to manage and update the derived encryption keys are also important issues.
The concept of the BE, which was initially suggested in 1991, has passed through considerable changes. The current BE presumes stateless receivers. The stateless receivers imply that secret keys of the users are not changed or updated at all as a session changes. A term ‘k-resilient’ is used in the security. The term ‘k-resilient’ denotes that k-ary revoked users cannot recover the original information even through collusion attacks. Typically, ‘r’ indicates the number of revoked users. Thus, ‘r-resilient’ implies that the information can be protected against collusion attacks by all of the revoked users.
The BE puts emphasis on a transmission overhead, a storage overhead, and a computation overhead. The transmission overhead denotes an amount of headers to be transmitted from the transmitter, the storage overhead denotes an amount of secret keys to be stored by the users, and the computation overhead denotes an amount of computations required to obtain a session key. Particularly, how to reduce the transmission overhead is an important issue.
Initially, the transmission overhead was in proportion to N which is the number of users, but now is reduced to be proportional to r which is the number of revoked users. As schemes in which the transmission overhead is proportional to r are suggested, it is desirable to determine how to reduce the transmission overhead to below r.
Various such schemes have been suggested. The Subset Difference (SD) method presented by Naor-Naor-Lotspiech shows the best results. As for n-ary users in total, the SD method requires the storage overhead O(log 1+en) and the transmission overhead O(2r−1).
However, the SD method is not efficient when used by a plurality of users.
As described above, since the first paper on BE, various algorithms have been suggested. Secret sharing, a subset cover-free system model, a tree structure, and the like have been suggested.
First, the secret sharing-based model will be schematically explained. The secret sharing-based model was first suggested by S. Berkovits in 1991 and then improved in a paper entitled “Efficient Trace and Revoke Schemes” by M. Noar and B. Pinkas in 2000. In “How to Broadcast a Secret” by S. Berkovits, a polynomial interpolation method and a vector-based secret sharing method were suggested.
In the polynomial interpolation method, a center, that is, a broadcast center or a transmitter, transmits points (xi, yi) to individual users via a secret channel. Here, xi, and (xi, yi) are secret keys of the individual users. The center selects a polynomial P having a random integer j and a degree t+j+1 to broadcast secret information S to t-ary authorized users of each session.
The polynomial P passes secret keys (xi, yi) of the t-ary authorized users and j-ary random points (x, y) and (O, S) that are not secret keys of other users. The center transmits t+j points and other points on the polynomial P. The t-ary authorized users know about a point (their own secret keys) besides the t+j points, and thus can restore the polynomial P having the degree t+j+1 and obtain the secret information S. However, the revoked users know only about the t+j points and thus cannot restore the polynomial P.
In the polynomial interpolation method, a transmission overhead is O(t+j+1), a storage overhead is O(1), and a computation overhead is about t3 times. Also, revocation is easy, collusion can be prevented, and traitor tracing is possible. However, the polynomial interpolation method is inefficient for a large number of users. Also, in a case where the polynomial interpolation method is repeatedly used, the polynomial interpolation method is not safe for multiple users. Thus, the polynomial interpolation method cannot be substantially used.
“Efficient Trace and Revoke Schemes” by M. Noar and B. Pinkas uses a threshold secret sharing method using a Lagrange's interpolation formula. In the method by Noar-Pinkas, an r polynomial can be restored with r+1 points on the r polynomial, but not with r points. In more detail, the center selects a random t polynomial P and offers different points on the random t polynomial P to individual users. If r-ary users are excluded, the center sums secret keys of the r-ary users and randomly selected t-r points and then broadcasts information as to t-ary points. As a result, although the excluded users sum their secret information, they know only about the t points. Non-excluded users can know about t+1 points and thus restore the polynomial P. A session key value P(0) is obtained using the polynomial P.
The Noar-Pinkas method facilitates revocation, prevents collusion, and enables traitor tracking. In particular, new users can be added, a transmission overhead is O(t), and a storage overhead is O(1). Thus, this method is considerably efficient. However, users more than t that are a first determined number cannot be excluded. In addition, a computation overhead necessary for computing a number of transmitted points or a polynomial depends on t. Thus, the Noar-Pinkas method is inefficient in many situations. Moreover, as t becomes large, computation time is increased. Thus, it is difficult to use the Noar-Pinkas method when a plurality of users are included.
In the subset cover-free system model, when a set of all users is S, a subset cover-free system is defined in a set whose members are subsets of the set S. If such a system can be found, a BE can be performed using the system. However, a storage overhead and a transmission overhead are about O(r log n). Thus, the subset cover-free system model is inefficient. Also, a method of expanding an 1-resilient model into a k-resilient model was introduced. An 1-resilient scheme can be relatively easily achieved. Thus, such an expansion appears meaningful. However, the efficiency of the 1-resilient scheme is greatly deteriorated during the expansion.
Methods using a tree structure have been recently explored. C. K. Wong, M. Gouda, and G. S. Lam suggested a Logical-tree-hierarchy (LTH) in 1998. However, in the LTH, a large number of users cannot be excluded in a one-time session. Also, as a session goes by, secret keys of users are changed. Thus, the LTH is distant from the current BE, which supposes stateless receivers. Thereafter, D. Naor, M. Naor, and J. Lotspiech suggested “Complete Subset (CS) Cover Scheme” and “Subset Difference (SD) Scheme” in 2001. On the supposition that a number of users is n and a number of excluded users is r in both methods, the center forms a binary tree having a height of log n and assigns corresponding secret keys to all nodes. Also, the center allocates users to leaf nodes one by one.
Describing the CS Cover scheme, each user receives and stores secrete keys of all nodes positioned on a path from a root node to the user's leaf node from the center. A subtree not including excluded users is called a CS. If such CSs are appropriately collected, the CSs can include only non-excluded users. At this time, if a session key is encrypted with a secret key corresponding to a root node of used CSs and then transmitted, authorized users can restore the session key. However, since excluded users are not included in any CSs, the excluded users cannot restore the session key.
FIG. 2 is a view illustrating the concept of the BE in which keys are assigned in a conventional tree structure. Referring to FIG. 2, nodes 220 receiving data through a BE scheme have their own key values 32 through 47 and key values of nodes connected to them on a tree.
For example, a node 34 has its own key value 34, a key value 209 of a node 17, a key value 204 of a node 8, a key value 202 of a node 4, and a key value 201 of a node 2. The node 34 shares the key value 209 of the node 17 with a node 35. Also, nodes 32, 33, and 35 share the key value 204 of the node 8 with the node 34.
If the nodes 32 through 47 represent all authorized users, a header of data includes the key value 201 of the node 2 so that the key value 201 of the node 2 is equally transmitted to all of the authorized users. Thus, the data may be transmitted securely.
If a user 36 is a revoked user, the key values relating to the node 36 should be updated since other users share key values of nodes related to the node 36. Specifically, key values 210, 205, 202, and 201 of the nodes 18, 9, 4, and 2 must be updated. The key values are updated from a lower node to an upper node.
Since the node 37 shares the key value 210 of the node 18, an updated key value 210 of the node 18 is encrypted as a key value of the node 37 and then transmitted to the node 37. The node 37 and the nodes 38 and 39 under the node 19 share the key value 205 of the node 9. Thus, an updated key value 205 of the node 9 is encrypted as the key value 210 of the node 18 that has been updated already and then transmitted to the node 37, and the updated key value 205 of the node 9 is encrypted as the key value 211 of the node 19 and then transmitted to the nodes 38 and 39.
The nodes 32, 33, 34, and 35 under the node 8 and the nodes 37, 38, and 39 under the node 9 share the key value 202 of the node 4. Thus, an updated key value 202 of the node 4 is encrypted as the key value 204 of the node 8 and then transmitted to the nodes 32 through 35. Also, the updated key value 202 of the node 4 is encrypted as the key value 205 of the node 9 and then transmitted to the nodes 37 through 39.
The nodes 32 through 39 under the node 4, except the node 36, and the nodes 40 through 47 under the node 5 share the key value 201 of the node 2. Thus, an updated key value 201 of the node 2 is encrypted as the key value 202 of the node 4 that has been updated and then transmitted to the users 32, 33, 34, 35, 37, 38, and 39. Also, the updated key value 201 of the node 2 is encrypted as the key value 203 of the node 5 and then transmitted to the nodes 40 through 47. Such a key updating process can block accesses of revoked users.
In the above-described method, that is, in the CS model, a transmission overhead is O(r log(n/r)) that is the number of CSs including only non-excluded users, and a storage overhead is O(log n).
An SD model is a modification of the above-described CS model, and requires a storage overhead of O(log2n) and a transmission overhead of O(2r−1) so as to drastically improve the transmission overhead. The SD model considers a subtree obtained by subtracting a subtree having a node w of a subtree, having a node v as a root node, as a root node from the corresponding subtree. Leaf nodes under this subtree are authorized users, and leaf nodes under the subtree having the node w as the root node are revoked users.
If revoked users are placed among an appropriate number of authorized users, the SD model may require a subset unlike the CD model requiring two or more subsets. In the SD model, hash values of keys assigned to nodes from the node v to the node w are obtained, and then values corresponding to the hash values are determined as session keys.
Each user has hash values of sibling nodes of each node on a path from the user's node to a leaf node as secret keys. Therefore, only authorized users can restore session keys due to the one-way nature of a hash function. In the SD model, a transmission overhead is O(2r−1), a storage overhead is O(log2n), and a computation overhead is O(log n).
An LSD model that is an improvement of the SD model was suggested in 2002. In the LSD model, a layer is used for each subtree to reduce a storage overhead to O(log3/2n). However, a transmission overhead doubles that of the SD model.
The BE models do not take account of a tree structure. In other words, the BE models are effective when a single transmitter transfers data to a plurality of receivers without intermediate devices as in the satellite broadcasting. Therefore, a demand arises for a novel efficient method for use in a multihop network environment.